//题目:
// 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
// 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
// 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    // int ret=INT_MAX;
    int arr[1001]={0};//arr[i]表示从第i个位置到楼顶的最小花费  记忆化搜索  √
public:
    int dfs(vector<int>& cost,int pos)
    {
        if(pos>=cost.size())  return 0;

        if(arr[pos]!=0)return arr[pos];

        //1.走一步
        int one_step=cost[pos]+dfs(cost,pos+1);
        //2.走两步
        int two_step=cost[pos]+dfs(cost,pos+2);

        arr[pos]=one_step<two_step?one_step:two_step;
        return arr[pos];
    }
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //a.全排列————超时！   优化 ————> 记忆化搜索  √
        // int tmp1=dfs(cost,0);
        // int tmp2=dfs(cost,1);

        // return tmp1<tmp2?tmp1:tmp2;

        //b.动态规划
        //1.创建dp数组   dp[i]表示:到达第i个位置所需的最小花费
        int dp[1001]={0};
        //2.初始化
        dp[0]=dp[1]=0; //到达第i个位置，但仍未从该位置出发，所需不需要花费体力
        //3.填表  dp[i]=dp[i-1]+cost[i-1] : dp[i-2]+cost[i-2]  中较小的那个
        for(int i=2;i<=cost.size();i++)
        {
            int one_step=dp[i-1]+cost[i-1];
            int two_step=dp[i-2]+cost[i-2];
            dp[i]=one_step<two_step?one_step:two_step;
        }
        //4.返回到达楼顶所需花费的最小体力
        return dp[cost.size()];
    }
};